#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

/**
 * @方法: 头插法迭代
 * @时间复杂度: o(n)
 * @空间复杂度: o(1)
 * @评价: 加入了 dummy 节点
 */
ListNode* reverseList(ListNode* head) {
    // 因为头节点可能会变，因此采用 dummy 节点
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    ListNode* cur = head;
    ListNode* pre = dummy;
    ListNode* next;
    while (cur && cur->next) {
        next = cur->next;
        cur->next = next->next;
        next->next = pre->next;
        pre->next = next;
    }
    return dummy->next;
}

/**
 * @方法: 普通迭代
 * @时间复杂度: o(n)
 * @空间复杂度: o(1)
 * @评价:
 */
ListNode* reverseList(ListNode* head) {
    ListNode* cur = head;
    ListNode* pre = nullptr;
    ListNode* next = nullptr;
    while (cur) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

/**
 * @方法: 递归
 * @时间复杂度: o(n)
 * @空间复杂度: o(n)
 * @评价:
 */
ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr)
        return head;
    ListNode* last = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return last;
}